\documentclass[10pt, a4paper]{article}

\usepackage{a4wide}
\usepackage{color}
\usepackage{amsmath,amssymb,epsfig,pstricks,xspace}
\usepackage{german,graphics}
\usepackage{dsfont}
\usepackage{amsfonts}
\usepackage{graphics, psfrag}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{enumitem} 
\usepackage{url}
\usepackage{array,dcolumn,booktabs}
\usepackage{pdflscape}
\usepackage{amsthm}



\newcounter{task}
\newcommand{\task}{\stepcounter{task}\paragraph{Task \thetask~--~
Solution}}

\usepackage{pifont}

\newcommand{\header}{
  \begin{center}
  \fbox{\parbox{11cm}{
    \begin{center}
      {\Large 1. Problem Session -- Solution\\ \vspace{0.2em}
        {\bf Secure Channels}\\ \vspace{0.7em} (Winter Term 2014/2015)\\
        \vspace{0.2em} \firstname \lastname\\
        \vspace{0.2em} \matriculationnumber
    }
    \end{center}
  }}
  \end{center}
}


%-------------------------------------------------------------------------------
%---------------------------- EDIT FROM HERE -----------------------------------
%-------------------------------------------------------------------------------

\newcommand{\firstname}{Vasilii }
\newcommand{\lastname}{Ponteleev}
\newcommand{\matriculationnumber}{115151}

\begin{document}
\pagestyle{plain}
\header




\task
Need help


\task
If the adversary is not able to
determine the oracles operation mode, it is assumed that she is not able to derive
any insights from observing encryptions and the encryption scheme is considered
to be secure in the sense of real-or-random security. 
\\[1\baselineskip]1) Oracle generates K and decides between real or random
\\[1\baselineskip]2) Let $M_i = M_j$, $c_0 = const$, $i \neq j$
\\[1\baselineskip] For two inputs we have $c_i$ and $c_j$, calculated as $c_i = E_k(c_0 \oplus M_i)$  
\\[1\baselineskip]3) if $c_i = c_j$ then oracle chose real, random otherwise
\\[1\baselineskip]This information can be retrieved because IV is a constant, which means the same message on the first iteration will result in the same ciphertext. If we see such situation it clearly means that real encryption occured, otherwise we get some random results which coudn't be achieved with constant IV.

\task  
Let M = $(m_1, m_2, m_3)$ - message. Pair $ (c_0,T)$  where T= CBC-MAC(M) , $c_0 \ne const$. So, to calculate CBC-MAC we need to do the following (it does not matter if there are 3 or n iterations)
\\[1\baselineskip]$c_1 = E_k(c_0 \oplus m_1)
\\[1\baselineskip]c_2 = E_k(c_1 \oplus m_2)
\\[1\baselineskip]T = c_3 = E_k(c_2 \oplus m_3)$  
\\[1\baselineskip] Assume we have $M^` = (m_1^`, m_2, m_3)$ - forged message, where $m_1^`\neq m_1$. So, on the first iteration CBC-MAC($M^`$) we have 
\\[1\baselineskip] $c_1^` = E_k(c_0^` \oplus m_1^`)$ 
\\[1\baselineskip] CBC-MAC($M^`$) = T then and only then, when \\[1\baselineskip] $c_0 \oplus m_1 = m_1` \oplus c_0`$ 
\\[1\baselineskip] $ c_0^` = m_1^` \oplus m_1 \oplus c_0$ 
\\[1\baselineskip] In other words, for every changed bit in message corresponding bit in $c_0$ should be changed.
 
\task
Given $M_1 = (m_{11}, m_{12}, ... , m_{1n})$, $ T_1 = CBC-MAC(M_1)$
 \\[1\baselineskip] $M_2 = (m_{21}, m_{22}, ... , m_{2k})$, $ T_2 = CBC-MAC(M_2)$, $ k \neq n$ 
\\[1\baselineskip] Let $M_f = (m_{11}, m_{12}, ... , m_{1n}, (m_{21} + T_1),  m_{22}, ... , m_{2k})$ - forged message.
 \\[1\baselineskip] CBC-MAC($M_f$) = $T_2$ because 
\\[1\baselineskip] on (n + 1) iteration $c_(m_{21}) = E_k(m_{21} \oplus T_1 \oplus T_1) = E_k(m_{21})$
\\[1\baselineskip] Thus, $|M_f| \neq |M_2|$, $CBC(M_f) = CBC(M_2)$
\\[1\baselineskip] which was to be demonstrated

\end{document}

